#include<iostream>
#include<string>
using namespace std;
int main(){
	string str,b;
	int n;
	cin>>n;
	while(n--){
		cin>>str;
		b="";
		for(int i=0;i<str.length();i++)
			switch(str[i]){
				case '0':b+="0000";
					break;
				case '1':b+="0001";
					break;
				case '2':b+="0010";
					break;
				case '3':b+="0011";
					break;
				case '4':b+="0100";
					break;
				case '5':b+="0101";
					break;
				case '6':b+="0110";
					break;
				case '7':b+="0111";
					break;
				case '8':b+="1000";
					break;
				case '9':b+="1001";
					break;
				case 'A':b+="1010";
					break;
				case 'B':b+="1011";
					break;
				case 'C':b+="1100";
					break;
				case 'D':b+="1101";
					break;
				case 'E':b+="1110";
					break;
				case 'F':b+="1111";
					break;
				default:break;
			}
		int k=3-b.length()%3,f;
		if(k!=3)
			while(k--)
				b="0"+b;
		for(int i=0;i<b.length()-2;i+=3){
			k=4*(b[i]-'0')+2*(b[i+1]-'0')+b[i+2]-'0';
			if(k!=0)
				f=1;
			if(f)
				cout<<k;
		}
		f=0;
		cout<<endl;
	}
	return 0;
} 
